//
// Created by 28735 on 2024/11/22.
//

#ifndef ADJACENTMAT_RIX_H
#define ADJACENTMAT_RIX_H

#include <list>
#include <stack>
#include <queue>

#define MAXSIZE 100

typedef enum { DG, DN, UDG, UDN } GraphKind;

/*  c implement*/

typedef struct
{
}Info;

typedef struct Vertex
{
    int location;
    //结点信息
    Info info;
} *Vertex_ptr, Vertexes[MAXSIZE];

//边矩阵
typedef struct Edge
{
    int value;

    //边结点信息
    Info info;
} Adjacent_matrix_c[MAXSIZE][MAXSIZE];

typedef struct
{
    Adjacent_matrix_c matrix{};
    Vertexes vertex{};
    int vertex_count{};
    int edge_count{};
    GraphKind kind = DG;
} MGraph_c;

class Traverse
{
public:
    //迭代实现
    static std::pmr::list<Vertex> DFS_recursion(const MGraph_c& graph)
    {
        std::pmr::list<Vertex> res(graph.vertex_count);
        bool visit[graph.vertex_count];
        bool* ptr = visit;
        for (int i = 0; i < graph.vertex_count; i++)
        {
            if (ptr[i] == false)
            {
                DFS_recursion_impl(graph, res, ptr, i);
            }
        }

        return res;
    }

    static void DFS_recursion_impl(const MGraph_c& graph, std::pmr::list<Vertex>& vec, bool* & visit,
                                   const int location)
    {
        vec.push_back(graph.vertex[location]);
        visit[location] = true;

        for (int i = 0; i < graph.vertex_count; i++)
        {
            if (i != location && graph.matrix[location][i].value != 0 && visit[i] != false)
            {
                DFS_recursion_impl(graph, vec, visit, i);
            }
        }
    }

    //非迭代实现
    static std::pmr::list<Vertex> DFS(const MGraph_c& graph)
    {
        std::pmr::list<Vertex> res(graph.vertex_count);

        bool visit[graph.vertex_count];
        std::stack<Vertex> vectex_stack;

        Vertex first = graph.vertex[0];
        first.location = 0;
        vectex_stack.push(first);

        while (!vectex_stack.empty())
        {
            Vertex vertex = vectex_stack.top();
            visit[vertex.location] = true;
            res.push_back(vertex);
            vectex_stack.pop();
            for (int i = 1; i < graph.vertex_count; i++)
            {
                if (graph.matrix[vertex.location][i].value == 1 && !visit[i] && i != vertex.location)
                {
                    vectex_stack.push(graph.vertex[i]);
                }
            }
        }

        return res;
    }


    //迭代实现


    //非迭代实现
    static std::pmr::list<Vertex> BFS(const MGraph_c& graph)
    {
        std::pmr::list<Vertex> res(graph.vertex_count);
        bool visit[graph.vertex_count];

        std::queue<Vertex> vertex_queue;
        Vertex vertex = graph.vertex[0];
        vertex.location = 0;
        vertex_queue.push(vertex);

        while (!vertex_queue.empty())
        {
            Vertex temp = vertex_queue.front();
            res.push_back(temp);
            vertex_queue.pop();
            visit[temp.location] = true;

            for (int i = 0; i < graph.vertex_count; i++)
            {
                if (graph.matrix[temp.location][i].value != 0 && visit[i])
                {
                    Vertex _temp = graph.vertex[i];
                    _temp.location = i;
                    vertex_queue.push(_temp);
                }
            }
        }
        return res;
    }
};


/*  c++ implement*/
class MGraph
{
public:
    Adjacent_matrix_c matrix{};
    Vertexes vertex{};
    int vertex_count{};
    int edge_count{};

public:
    explicit MGraph() = default;

    ~MGraph() = default;
};

#endif //ADJACENTMAT_RIX_H
